class 并查集:
    def __init__(self, n: int):
        self.fa = list(range(n + 1))

    def find(self, x: int):
        """
        查找x属于哪个集合
        """
        if x == self.fa[x]:
            return x
        else:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]

    def union(self, x: int, y: int):
        """
        将x所在集合合并到y所在集合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.fa[x] = y


if __name__ == "__main__":  # 测试
    bcj = 并查集(10)
    print([bcj.find(i) for i in range(1, 11)])
    bcj.union(8, 9)
    print([bcj.find(i) for i in range(1, 11)])
    bcj.union(9, 1)
    print([bcj.find(i) for i in range(1, 11)])
